#define _CRT_SRCURE_NO_WARNINGS 1
#pragma  warning (disable:4996)

#include "UnionFindSet.h"
#include "Graph.h"
using namespace matrix;
void TestGraph1()
{
	matrix::Graph<char, int> g("ABCDEFGHI", 9);
	g.AddEdge('A', 'B', 1);
	g.AddEdge('A', 'D', 1);
	g.AddEdge('B', 'E', 1);
	g.AddEdge('E', 'G', 1);
	g.AddEdge('B', 'C', 1);
	g.AddEdge('D', 'F', 1);
	g.AddEdge('C', 'F', 1);
	g.AddEdge('F', 'H', 1);
	g.AddEdge('H', 'I', 1);
	g.Print();
	g.dfs('A'); cout << endl;
	g.bfs('A');
}
void TestGraphMinTree()
{
	const char* str = "abcdefghi";
	matrix::Graph<char, int> g(str, strlen(str));
	g.AddEdge('a', 'b', 4);
	g.AddEdge('a', 'h', 8);
	g.AddEdge('b', 'c', 8);
	g.AddEdge('b', 'h', 11);
	g.AddEdge('c', 'i', 2);
	g.AddEdge('c', 'f', 4);
	g.AddEdge('c', 'd', 7);
	g.AddEdge('d', 'f', 14);
	g.AddEdge('d', 'e', 9);
	g.AddEdge('e', 'f', 10);
	g.AddEdge('f', 'g', 2);
	g.AddEdge('g', 'h', 1);
	g.AddEdge('g', 'i', 6);
	g.AddEdge('h', 'i', 7);

	matrix::Graph<char, int> kminTree(g);
	cout << "Kruskal:" << endl << g.Kruskal(kminTree) << endl;

	matrix::Graph<char, int> pminTree(g);
	cout << "Prim:" << endl << g.Prim(pminTree, 'a') << endl;
}
void TestDijkstra()
{
	const char* str = "syztx";
	matrix::Graph<char, int, true> g(str, strlen(str));
	g.AddEdge('s', 't', 10);
	g.AddEdge('s', 'y', 5);
	g.AddEdge('y', 't', 3);
	g.AddEdge('y', 'x', 9);
	g.AddEdge('y', 'z', 2);
	g.AddEdge('z', 's', 7);
	g.AddEdge('z', 'x', 6);
	g.AddEdge('t', 'y', 2);
	g.AddEdge('t', 'x', 1);
	g.AddEdge('x', 'z', 4);
	vector<int> shortPath;
	vector<int> prev;
	g.Dijkstra('s', shortPath, prev);
	for (auto v : shortPath) cout << v << " ";
	cout << endl;
	for (auto v : prev) cout << v << " ";
	cout << endl;
}
void TestFloydWarshall()
{
	const char* str = "12345";
	matrix::Graph<char, int, true> g(str, strlen(str));
	g.AddEdge('1', '2', 3);
	g.AddEdge('1', '3', 8);
	g.AddEdge('1', '5', -4);
	g.AddEdge('2', '4', 1);
	g.AddEdge('2', '5', 7);
	g.AddEdge('3', '2', 4);
	g.AddEdge('4', '1', 2);
	g.AddEdge('4', '3', -5);
	g.AddEdge('5', '4', 6);
	vector<vector<int>> shortPath;
	vector<vector<int>> prev;
	g.FloydWarshall(shortPath, prev);
	for (int i = 0; i < shortPath.size(); i++)
	{
		for (int j = 0; j < shortPath.size(); j++)
		{
			if (shortPath[i][j] == INT_MAX) cout << "* ";
			else cout << shortPath[i][j] << " ";
		}
		cout << endl;
	}
	cout << "-----------------" << endl << endl;
	for (int i = 0; i < prev.size(); i++)
	{
		for (int j = 0; j < prev.size(); j++) cout << prev[i][j] << " ";
		cout << endl;
	}
}
int main()
{
	TestFloydWarshall();
	return 0;
}